1. Field of the Invention
This invention relates to a method and apparatus for digital communications, and more particularly to a method and apparatus for reordering sequential information which has been received out of sequence.
2. Description of Related Art
In the computer industry, a number of protocols exist for moving mass quantities of data over high-speed digital networks. For example, Fibre Channel is emerging as a standard for interconnecting workstations and peripherals within a computer system. Use of the Fibre Channel standard allows as much as 200 Mbytes of data to be transferred in as little as two seconds. Fibre Channel is considered by some to be a high-speed local-area network standard. Fibre Channel is a switched medium. This means that packets of data are transferred by each of the users. Data is transported in packets of two kilobytes or smaller. These packet of data are referred to as "frames". Sequences comprise one or more frames which must be assembled in a predetermined order before the sequence can be considered complete at the receiving device.
FIG. 1 is an illustration of the frame format for a Fibre Channel frame. The first four bytes of the frame are allocated to a "Start-of-Frame" field 101. The Start-of-Frame field 101 is a pattern of data that indicates that a frame follows. The next twenty-four bytes are allocated to a "Frame-Header" field 103. The Frame-Header field 103 includes four subfields that, taken together, uniquely identify the frame. The first of these subfields is a source identification subfield (S-ID). The S-ID subfield is three bytes of information that identifies the device from which the frame originated. The second of these subfields is a destination identification subfield (D-ID). The D-ID subfield is three bytes of information that identifies the device that is intended to receive the frame. The third of these subfields is a sequence identification subfield (SEQ-ID). The SEQ-ID subfield is three bytes that identify the particular sequence with which the frame is associated. The fourth of these subfields is a sequence count subfield (SEQ-CNT). The SEQ-CNT subfield determines the relative order of the frame within the sequence with respect to each of the other frames of that particular sequence.
The next 0-2112 bytes of the frame are allocated to the payload field 105 (i.e., the field that carries the information that is to be transmitted from the source device to the destination device). The next four bytes of the frame are allocated to a cyclical redundancy code (CRC) field 107 which permits errors in the data of the frame to be detected. The last four bytes of the frame are allocated to an "End-of-Frame" field 109.
One problem with communications protocols, such as Fibre Channel, is that data must be received in a predetermined order at the receiving end of a communications link. However, requirements of the communications link can prevent the data from arriving in order. For example, the source device may detect an error in the frame of information and transmit the next frame before correcting the error. After the error has been corrected, the frame that was in error is retransmitted out of order. Transmission of the next frame in order before correction of an error in a previously transmitted frame allows the source device to continue doing productive work (i.e., sending frames of data) while correcting a detected error. In another example, the source device may send frames in the proper order. However, frames may take different paths to the destination device. The result of different transmission delays over the different paths may result in the frames arriving out of order.
While transmission of subsequent frames after detecting an error in a previously transmitted frame, and transmission of frames over different paths, may cause frames to be received out of order, and thus burden the destination device with the task of reordering the frames, such operation allows the source device to exploit the best delivery path and continue to transmit frames of data uninterrupted by errors.
Existing mechanisms for re-sequencing frames either penalize the source device by requiring manual or intelligent intervention at reduced performance, or penalize the system by requiring the sender to re-send the sequential information until it arrives at the destination in the correct order. For example, the TCP (Transport Control Protocol) Transport Layer protocol is a software mechanism that uses the services of Internet Protocol (IP) to provide reliable, ordered stream data delivery. The TCP software process in the receiving system checks each received segment to ensure that there are no missing, duplicated, or out of order segments. This system requires the receiver to intelligently intervene and thus reduces the performance of the receiver.
Accordingly, there is a need for a simple means for reordering frames received by a destination source to conform to the order intended by the source device which does not impact the efficiency and speed of the data communication.